//! Inodes.
//!
//! An inode describes a single unnamed file. The inode disk structure holds metadata: the file's type,
//! its size, the number of links referring to it, and the list of blocks holding the file's content.
//!
//! The inodes are laid out sequentially on disk at block sblock.inodestart. Each inode has a number,
//! indicating its position on the disk.
//!
//! The kernel keeps a table of in-use inodes in memory to provide a place for synchronizing access to
//! inodes used by multiple processes. The in-memory inodes include book-keeping information that is not
//! stored on disk: ip.ref and ip.valid.
//!
//! An inode and its in-memory representation go through a sequence of states before they can be used by
//! the rest of the file system code.
//!
//! * Allocation: an inode is allocated if its type (on disk) is non-zero. alloc() allocates, and put()
//!   frees if the reference and link counts have fallen to zero.
//!
//! * Referencing in table: an entry in the inode table is free if ip.ref is zero. Otherwise ip.ref
//!   tracks the number of in-memory pointers to the entry (open files and current directories). get()
//!   finds or creates a table entry and increments its ref; put() decrements ref.
//!
//! * Valid: the dinode information (type, size, &c) in an inode table entry is only correct when
//!   ip.valid is true. lock() reads the dinode from the disk and sets ip.valid, while put() clears
//!   ip.valid if ip.ref has fallen to zero.
//!
//! * Locked: file system code may only examine and modify the information in an inode and its content if
//!   it has first locked the inode.
//!
//! Thus a typical sequence is:
//!   ip = get(inum)
//!   defer ip.put()
//!   ip.lock()
//!   defer ip.unlock()
//!   ... examine and modify ip.inode ...
//!
//! lock() is separate from get() so that system calls can get a long-term reference to an inode (as for
//! an open file) and only lock it for short periods (e.g., in read()). The separation also helps avoid
//! deadlock and races during pathname lookup. get() increments ip.ref so that the inode stays in the
//! table and pointers to it remain valid.
//!
//! Many internal file system functions expect the caller to have locked the inodes involved; this lets
//! callers create multi-step atomic operations.
//!
//! The `spin` lock protects the allocation of inodes entries. Since ip.ref indicates whether an entry is
//! free, and ip.dev and ip.inum indicate which i-node an entry holds, one must hold `spin` lock while
//! using any of those fields.
//!
//! An ip.sleep sleep-lock protects all inodes fields other than dev, inum and ref. One must hold
//! ip.sleep in order to read or write that inode's ip.valid and ip.disk.
const Inode = @This();

/// directory inode
const Dir = Inode;

/// Device number
dev: u32 = 0,
/// Inode number
inum: u32 = 0,
/// Reference count
ref: u32 = 0,

/// protects everything below here
sleep: os.Lock.Sleep = .init("inode"),

/// inode has been read from disk?
valid: bool = false,
/// copy of disk inode
disk: Dinode = .{},

pub const Type = enum(u16) {
    none = 0,
    dir = 1,
    file = 2,
    device = 3,
    symlink = 4,

    _, // invalid but useful for byte order conversion
};

/// Inode block structure layout:
///
/// The inode uses a multi-level index structure to store block pointers:
/// - l0 direct block pointers (immediately addressable)
/// - l1 singly-indirect block pointer (points to a block of 256 direct pointers)
/// - l2 doubly-indirect block pointer (points to a block of 256 indirect pointers,
///   each pointing to another block of 256 direct pointers)
///
/// +----------+------------------>  direct (l0 * 1)
/// |          +--+--------------->  singly-indirect (l1 * 256)
/// |          |  +-+------------->  doubly-indirect (l2 * 256 * 256)
/// +----------+--+-+
///     l0      l1 l2
pub const Dinode = extern struct {
    type: Type = .none,
    major: u16 = 0,
    minor: u16 = 0,
    nlink: u16 = 0,
    size: u32 = 0,
    addrs: [l0 + l1 + l2]Block = @splat(.empty),

    comptime {
        std.debug.assert(@sizeOf(Dinode) == 64);
        std.debug.assert(fs.BSIZE % @sizeOf(Dinode) == 0);
    }

    /// Number of directly addressable data blocks (L0)
    pub const l0 = 7;
    /// Number of single-indirect blocks (L1)
    pub const l1 = 4;
    /// Number of double-indirect blocks (L2)
    pub const l2 = 2;

    /// Number of data blocks addressable per indirect block (L1)
    pub const per_l1 = fs.blocks_per_indirect;
    /// Number of data blocks addressable per double-indirect block (L2)
    pub const per_l2 = fs.blocks_per_indirect * fs.blocks_per_indirect;

    pub const l0_blocks = l0 * 1; // direct
    pub const l1_blocks = l1 * per_l1; // indirect
    pub const l2_blocks = l2 * per_l2; // double-indirect

    /// total number of blocks
    pub const total_blocks = l0_blocks + l1_blocks + l2_blocks;

    /// Resolves a logical block number to its position in the multi-level index
    /// Returns a tuple containing the indices needed to access the block through:
    /// [direct_idx, indirect_idx, dbl_indirect_idx]
    pub fn blockidx(block: u32) [3]?usize {
        var num = block;
        if (num < l0_blocks)
            return .{ num, null, null };

        num -= l0_blocks;
        if (num < l1_blocks)
            return .{ l0 + num / per_l1, num % per_l1, null };

        num -= l1_blocks;
        if (num < l2_blocks)
            return .{
                l0 + l1 + num / per_l2,
                num % per_l2 / per_l1,
                num % per_l2 % per_l1,
            };

        @panic("block: out of range");
    }
};

/// protects the allocation of inodes entries
var spin: os.Lock.Spin = .init("itable");
var inodes: [os.NINODE]Inode = @splat(.{});

/// Allocate a new inode of the given type. Returns a referenced but unlocked inode, or error if there is
/// no free inode. Caller must call put() to release the reference when done.
pub fn alloc(t: Type) error{NoSpaceLeft}!*Inode {
    for (1..fs.sblock.ninodes) |inum| {
        var buf: *Buffer = .read(fs.sblock.inodeBlock(@intCast(inum)));
        defer buf.release();

        const disk_inodes: [*]Dinode = @ptrCast(&buf.data);
        const disk = &disk_inodes[inum % fs.IPB];

        if (disk.type == .none) { // a free node
            disk.* = .{};
            disk.type = t;
            log.write(buf); // mark it allocated on the disk
            return get(@intCast(inum));
        }
    }

    std.log.scoped(.inode).err("no inodes", .{});
    return error.NoSpaceLeft;
}

/// Find the inode with number inum on device dev and return the in-memory copy. Does not lock the inode
/// and does not read it from disk. Caller must call put() to release the reference when done.
pub fn get(inum: u32) *Inode {
    spin.acquire();
    defer spin.release();

    // Is the inode already in the table?
    var empty: ?*Inode = null;
    var inode = for (&inodes) |*ino| {
        if (ino.ref > 0 and ino.inum == inum) {
            ino.ref += 1;
            return ino;
        }
        if (empty == null and ino.ref == 0) // Remember empty slot.
            empty = ino;
    } else empty orelse @panic("get: no inodes");

    // Recycle an inode entry.
    inode.inum = inum;
    inode.ref = 1;
    inode.valid = false;
    return inode;
}

/// Increments the reference count for this inode. Returns the same inode to enable chaining: `ip = ip1.dup()`.
/// Caller must call put() to release the reference when done.
pub fn dup(self: *Inode) *Inode {
    spin.acquire();
    defer spin.release();
    self.ref += 1;
    return self;
}

/// Drop a reference to an in-memory inode. If this was the last reference, the inode table entry can be
/// recycled. If the inode has no links and this was the last reference, frees the disk inode and its
/// data. All calls to put() must be inside a transaction when freeing is possible.
pub fn put(self: *Inode) void {
    spin.acquire();
    defer spin.release();

    if (self.ref == 1 and self.valid and self.disk.nlink == 0) {
        // inode has no links and no other references: truncate and free.

        // ref == 1 means no other process can have ip locked, so this sleep.acquire() won't block (or deadlock).
        self.sleep.acquire();
        spin.release();

        self.truncate();
        self.disk.type = .none;
        self.flush();
        self.valid = false;

        self.sleep.release();
        spin.acquire();
    }

    self.ref -= 1;
}

/// Lock the given inode. Reads the inode from disk if necessary.
pub fn lock(self: *Inode) void {
    assert(self.ref > 0);
    self.sleep.acquire();
    if (self.valid) return;

    var buf: *Buffer = .read(fs.sblock.inodeBlock(self.inum));
    const disk_inodes: [*]Dinode = @ptrCast(&buf.data);
    const disk = &disk_inodes[self.inum % fs.IPB];

    self.disk = disk.*;
    buf.release();

    self.valid = true;
    assert(self.disk.type != .none);
}

// Unlock the given inode.
pub fn unlock(self: *Inode) void {
    assert(self.sleep.holding() and self.ref > 0);
    self.sleep.release();
}

// Common idiom: unlock, then put.
pub fn unlockput(self: *Inode) void {
    self.unlock();
    self.put();
}

/// Maps a logical block number to a physical block, allocating one if necessary. Returns null if
/// allocation fails due to lack of disk space.
fn bmap(self: *Inode, blockno: u32) error{ FileTooBig, NoSpaceLeft }!Block {
    if (blockno >= Dinode.total_blocks) return error.FileTooBig;
    const idx: [3]?usize = Dinode.blockidx(blockno);

    var addr: Block = self.disk.addrs[idx[0].?];
    if (addr.index == 0) {
        addr = try Block.alloc();
        self.disk.addrs[idx[0].?] = addr;
    }

    // indirect block
    if (idx[1]) |idx1| {
        const buf: *Buffer = .read(addr);
        defer buf.release();

        const blocks: *[fs.blocks_per_indirect]Block = @ptrCast(&buf.data);
        addr = blocks[idx1];
        if (addr.index == 0) {
            addr = try Block.alloc();
            blocks[idx1] = addr;
            log.write(buf);
        }

        // doubly-indirect block
        if (idx[2]) |idx2| {
            const buf2: *Buffer = .read(addr);
            defer buf2.release();

            const blocks2: *[fs.blocks_per_indirect]Block = @ptrCast(&buf2.data);
            addr = blocks2[idx2];
            if (addr.index == 0) {
                addr = try Block.alloc();
                blocks2[idx2] = addr;
                log.write(buf2);
            }
        }
    }

    assert(addr.index != 0);
    return addr;
}

/// Read data from inode. Caller must hold lock.
pub fn read(self: *Inode, w: *std.Io.Writer, offset: u32, len: usize) !usize {
    var n = len;
    var off = offset;

    if (off > self.disk.size or off + n < off)
        return 0;
    if (off + n > self.disk.size)
        n = self.disk.size - offset;

    var nbytes: u32 = 0;
    var total: usize = 0;

    while (total < n) : ({
        total += nbytes;
        off += nbytes;
    }) {
        const block = try self.bmap(off / fs.BSIZE);

        const buf: *Buffer = .read(block);
        defer buf.release();

        nbytes = @min(n - total, fs.BSIZE - off % fs.BSIZE);
        try w.writeAll(buf.data[off % fs.BSIZE ..][0..nbytes]);
    }

    try w.flush();
    return total;
}

/// Read struct from inode. Caller must hold lock.
pub fn readStruct(self: *Inode, T: type, offset: u32) !T {
    const p = os.proc.current().?;
    const size = @sizeOf(T);

    var s: T = undefined;
    var writer = p.writer(.kernel, &.{}, @ptrCast(&s));
    const nbytes = try self.read(&writer.io_w, offset, size);
    if (nbytes != size) return error.ReadFailed;
    return s;
}

/// Write data to inode. Caller must hold lock. If the return value is less than the requested n, there
/// was an error of some kind.
pub fn write(self: *Inode, r: *std.Io.Reader, offset: u32, len: usize) !void {
    var off = offset;

    if (off > self.disk.size or off + len < off)
        return error.InvalidArgument;
    if (off + len > Dinode.total_blocks * fs.BSIZE)
        return error.FileTooBig;

    var total: usize = 0;
    var nbytes: u32 = 0;

    while (total < len) : ({
        total += nbytes;
        off += nbytes;
    }) {
        const block = try self.bmap(off / fs.BSIZE);

        const buf: *Buffer = .read(block);
        defer buf.release();

        nbytes = @min(len - total, fs.BSIZE - off % fs.BSIZE);
        try r.readSliceAll(buf.data[off % fs.BSIZE ..][0..nbytes]);
        log.write(buf);
    }

    if (off > self.disk.size) self.disk.size = off;

    // write the i-node back to disk even if the size didn't change because the loop above might have
    // called bmap() and added a new block to self.addrs[].
    self.flush();
    if (total != len) @panic("write: short write");
}

/// Copy a modified in-memory inode to disk. Caller must hold lock. Must be called after every change to
/// an Inode field that lives on disk.
pub fn flush(self: *Inode) void {
    var buf: *Buffer = .read(fs.sblock.inodeBlock(self.inum));
    defer buf.release();

    const disk_inodes: [*]Dinode = @ptrCast(&buf.data);
    const disk = &disk_inodes[self.inum % fs.IPB];

    disk.* = self.disk;
    log.write(buf);
}

/// Truncate inode (discard contents). Caller must hold lock.
pub fn truncate(self: *Inode) void {
    for (&self.disk.addrs, 0..) |*addr, i| {
        if (addr.index == 0) continue;

        // indirect block
        if (i >= Dinode.l0) {
            const buf: *Buffer = .read(addr.*);
            defer buf.release();

            const blocks: *[fs.blocks_per_indirect]Block = @ptrCast(&buf.data);
            for (blocks) |block| {
                if (block.index == 0) continue;
                defer block.free();

                // doubly-indirect block
                if (i >= Dinode.l0 + Dinode.l1) {
                    const buf2: *Buffer = .read(block);
                    defer buf2.release();

                    const blocks2: *[fs.blocks_per_indirect]Block = @ptrCast(&buf2.data);
                    for (blocks2) |block2| {
                        if (block2.index != 0) block2.free();
                    }
                }
            }
        }

        addr.free();
        addr.* = .empty;
    }

    self.disk.size = 0;
    self.flush();
}

pub const Stat = extern struct {
    /// File system's disk device
    dev: u32 = 0,
    /// Inode number
    ino: u32 = 1,
    /// Type of file
    type: Type = .none,
    /// Number of links to file
    nlink: u16 = 0,
    /// Size of file in bytes
    size: u32 = 0,
};

// Copy stat information from inode. Caller must hold lock.
pub fn stat(self: *Inode) Stat {
    return .{
        .dev = self.dev,
        .ino = self.inum,
        .type = self.disk.type,
        .nlink = self.disk.nlink,
        .size = self.disk.size,
    };
}

/// Directory is a file containing a sequence of Dirent structures.
pub const Dirent = extern struct {
    pub const DIRSIZ = 14;
    pub const Name = os.lib.Name(DIRSIZ);

    /// current dir and parent dir
    pub const dot_dirs = [2]Name{ .cwd, .parent };

    inum: u16 = 0,
    name: Name = .empty,

    comptime {
        std.debug.assert(fs.BSIZE % @sizeOf(Dirent) == 0);
    }
};

/// Returns the full pathname for the given inode, storing it in the buffer. Caller must hold the
/// directory lock.
pub fn getpath(dir: *Dir, buffer: []u8) ![]const u8 {
    assert(dir.disk.type == .dir);

    var arena: std.heap.ArenaAllocator = .init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var stack: std.ArrayList(Dirent.Name) = .empty;
    defer stack.deinit(allocator);

    var inode = dir.dup();
    defer inode.put();
    inode.lock();
    defer inode.unlock();

    while (inode.inum != fs.ROOTINO) {
        const inum, _ = inode.childInode(.parent) orelse unreachable;
        const parent = get(inum);
        parent.lock();

        const name = parent.childName(inode.inum) orelse unreachable;
        try stack.append(allocator, name);

        inode.unlockput();
        inode = parent;
    }

    var path: std.ArrayList(u8) = .empty;
    defer path.deinit(allocator);

    if (stack.items.len == 0) {
        try path.append(allocator, '/');
    } else while (stack.pop()) |name| {
        try path.append(allocator, '/');
        try path.appendSlice(allocator, name.get());
    }

    return std.fmt.bufPrint(buffer, "{s}", .{path.items});
}

/// Scans a directory sequentially, applying a match function to each entry.
/// Returns the first non-null result from the match function, or null if no matches found.
/// Parameters:
///   - `match`: Function that examines directory entries and returns either a value or null
///   - `data`: Contextual data passed through to the match function
/// Returns: The match function's return type or null if no match found
fn search(dir: *Dir, match: anytype, data: anytype) @typeInfo(@TypeOf(match)).@"fn".return_type.? {
    assert(dir.disk.type == .dir);

    var offset: u32 = 0;
    while (offset < dir.disk.size) : (offset += @sizeOf(Dirent)) {
        const de = dir.readStruct(Dirent, offset) catch unreachable;
        return match(de, offset, data) orelse continue;
    }
    return null;
}

/// Searches a directory for a child entry with the specified inode number and returns its name.
/// Caller must hold the directory lock.
pub fn childName(dir: *Dir, inum: u32) ?Dirent.Name {
    return dir.search(matchInum, inum);
}

/// Match function for finding directory entries by inode number.
fn matchInum(de: Dirent, _: u32, inum: u32) ?Dirent.Name {
    if (de.inum == 0) return null; // unallocated entries
    if (!de.name.eql(.parent) and !de.name.eql(.cwd) and de.inum == inum)
        return de.name;
    return null;
}

/// Look for a directory for an entry matching the given name. If found, returns both the entry's inode
/// number and its byte offset within the directory. Caller must hold the directory lock.
pub fn childInode(dir: *Dir, name: Dirent.Name) ?struct { u32, u32 } {
    return dir.search(matchName, name);
}

/// Match function for finding directory entries by name.
fn matchName(de: Dirent, offset: u32, name: Dirent.Name) ?struct { u32, u32 } {
    if (de.inum == 0) return null; // unallocated entries
    if (de.name.eql(name))
        return .{ de.inum, offset };
    return null;
}

/// Write a new directory entry (name, inum) into the directory `dir`. Caller must hold the directory
/// lock.
pub fn addEntry(dir: *Dir, name: Dirent.Name, inum: u32) !void {
    // Check that name is not present.
    if (dir.childInode(name) != null) {
        return error.PathAlreadyExists;
    }

    const de: Dirent = .{
        .name = .init(name.get()),
        .inum = @intCast(inum),
    };

    // Look for an empty dir_entry.
    const offset = dir.search(matchEmpty, {}) orelse dir.disk.size;
    const p = os.proc.current().?;
    var reader = p.reader(.kernel, &.{}, @ptrCast(&de));
    try dir.write(&reader.io_r, offset, @sizeOf(Dirent));
}

/// Match function for finding empty directory slots.
fn matchEmpty(de: Dirent, offset: u32, _: void) ?u32 {
    if (de.inum == 0) return offset; // unallocated entries
    return null;
}

/// Is the directory empty except for "." and ".." ?
/// Caller must hold the directory lock.
pub fn isEmpty(dir: *Dir) bool {
    return if (dir.search(matchNonEmpty, {}) == null) true else false;
}

/// Match function for detecting non-special directory entries.
fn matchNonEmpty(de: Dirent, _: u32, _: void) ?void {
    if (!de.name.eql(.parent) and !de.name.eql(.cwd) and de.inum != 0) return;
    return null;
}

const std = @import("std");
const os = @import("../os.zig");
const fs = @import("../fs.zig");
const log = @import("log.zig");
const Buffer = @import("Buffer.zig");
const Block = fs.Block;
const Direction = os.proc.Proc.Direction;
const assert = std.debug.assert;
